/**
* 二叉树的层次遍历(使用环形队列辅助)
*/
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define bool int
#define true !0
#define false 0

//定义一线性循环队列
typedef struct QNode {
    int data[MAXSIZE];
    int front;
    int rear;
} QNode, *Queue;

//定义一个二叉树结点
typedef struct BNode {
    int data;
    struct BNode *LChild;
    struct BNode *RChild;
} BNode, *BTree;

//队列初始化
void initQueue(Queue &queue);

//判断队列是否为空
bool queueIsEmpty(Queue &queue);

//入队操作
bool enQueue(Queue &queue, int data);

//出队操作
int deQueue(Queue &queue);

int main() {
    //初始化队列
    Queue queue;
    initQueue(queue);

    BTree bTree = (BNode *) malloc(sizeof(BNode));


    bTree->data = 1;
    bTree->LChild = (BNode *) malloc(sizeof(BNode));
    bTree->LChild->data = 2;
    bTree->RChild = (BNode *) malloc(sizeof(BNode));
    bTree->RChild->data = 3;
    bTree->RChild->LChild = NULL;
    bTree->RChild->LChild = NULL;
    bTree->LChild->LChild = (BNode *) malloc(sizeof(BNode));
    bTree->LChild->LChild->data = 4;
    bTree->LChild->RChild = NULL;
    bTree->LChild->LChild->LChild = NULL;
    bTree->LChild->LChild->RChild = NULL;

    //头结点先入队列
    enQueue(queue, bTree->data);
    while (queue->front < queue->rear) {
        //头结点出队列，其对用的孩子如果存在则入队列
        int data = deQueue(queue);
        printf("%d ", data);
        //左右孩子如果存在则入队列
        if (bTree->LChild) enQueue(queue, bTree->LChild->data);
        if (bTree->RChild) enQueue(queue, bTree->RChild->data);
    }
    return 0;
}


void initQueue(Queue &queue) {
    queue->front = queue->rear = 0;
}

bool queueIsEmpty(Queue &queue) {
    return (queue->front == queue->rear) ? true : false;
}

bool enQueue(Queue &queue, int data) {
    //判断队列是否已满
    if ((queue->rear + 1) % MAXSIZE == queue->front) return false;
    queue->data[queue->rear] = data;
    queue->rear = (queue->rear + 1) % MAXSIZE;
    return true;
}

int deQueue(Queue &queue) {
    //判断队列是否为空
    if (queueIsEmpty(queue)) return -1;
    int data = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAXSIZE;
    return data;
}